POI2008 Mafia

POI
基环外向树, 拓扑排序, 贪心

POI2008 Mafia

题目大意：

有n个人，每一个人有一把手枪。一开始，所有的人都选定一个人瞄准(有可能瞄准自己)。然后他们按照某一个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死掉的人也不同。问最后死亡人数的最小和最大可能值。

( $n\le 10^6$ )

题解：

首先很容易看出，图是一个基环外向树，那么我们就可以借助一些基环外向树的性质来解题了。

对于最大的可能人数，我们比较好得到。只要让存活人数最少就可以了，那么就让那些一定不会死的人活下来，其他人都可以杀掉。

不会死的人有两种：

  1. 入度为0的人。由于没有人拿枪瞄准他们，显然不会死。
  2. 当一个基环外向树没有”树枝”，而只有中间那一个环时，我们没有办法将环上的人全部杀完，总要留下一个。留下的那个就可以不用死。(中间的环不能是自环，不然当然可以把环上的人杀完)

利用拓扑排序随便搞一下，这部分就可以解决了。

接下来看看最小的可能人数：

一个人会不会死关键看是否有一个没死的人拿枪指着他。

也就是说，如果有一个人没死，那么被他指的人一定会死。

首先，入度为零的人，一定不会死，但是被他指的人全都会死。

为了让活着的人尽量多，我们不妨让死了的人都不开枪。

那么对于一个必死的人，他所瞄准的人都少了一次被杀死的机会，可以把它们的入度减一。

如果入度减为了零，说明所有的威胁都被排除，此人已经死不了了。

由此，我们可以把基环外向树上的”树枝”全部清理掉。

对于留下的环，我们从环上任意一个人开始，让他死，那么环也就可以流动起来了。

其实最小值也可以用树形dp来写。

题目转化一下就可以变为：

我们把基环外向树的边都变为双向的。然后在树上取一些点(表示这些点活着)，且两个被取的点不能相邻，最大化取的点的数量。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<queue>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=1000005;
int n,aim[N],cnt[N],ans;
bool used[N];
void work(int p,int c){
	if(used[p])return;
	used[p]=true;
	ans+=c;
	if(!(--cnt[aim[p]])||c)work(aim[p],c^1);
}
int solve_min(){
	ans=0;
	memset(cnt,0,sizeof(cnt));
	memset(used,0,sizeof(used));
	for(int i=1;i<=n;i++)cnt[aim[i]]++;
	for(int i=1;i<=n;i++)
		if(!cnt[i])work(i,1);
	for(int i=1;i<=n;i++)work(i,0);
	return n-ans;
}
queue<int>que;
void check_loop(int p){
	bool flag=false;
	for(int pre=p;flag|=used[p],aim[p]!=pre;cnt[aim[p]]--,p=aim[p]);
	if(!flag)ans++;
}
int solve_max(){
	ans=0;
	memset(cnt,0,sizeof(cnt));
	memset(used,0,sizeof(used));
	for(int i=1;i<=n;i++)cnt[aim[i]]++;
	while(!que.empty())que.pop();
	for(int i=1;i<=n;i++)
		if(!cnt[i])que.push(i),ans++;
	while(!que.empty()){
		int p=que.front();que.pop();
		if(!(--cnt[aim[p]]))que.push(aim[p]);
		else used[aim[p]]=true;
	}
	for(int i=1;i<=n;i++)
		if(cnt[i]&&i!=aim[i])check_loop(i);
	return n-ans;
}
int solve(){
	printf("%d %d\n",solve_min(),solve_max());
	return 0;
}
int main(){
	Rd(n);
	for(int i=1;i<=n;i++)Rd(aim[i]);
	return solve();
}
分享到 评论